package nf;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import nf.graph.Graph;
import nf.graph.Delta;
import nf.graph.Node;
import nf.traversal.Traverser;
import nf.traversal.TraverserFactory;
import nf.utility.UtilityCalculator;
import nf.util.Rational;

public abstract class EdgeGame extends Game
{
	protected TraverserFactory traverserFactory;
	protected UtilityCalculator utilCalc;
	
	protected EdgeGame(TraverserFactory traverserFactory,
		UtilityCalculator utilCalc)
	{
		setTraverserFactory(traverserFactory);
		setUtilityCalculator(utilCalc);
	}
	
	/**
	 * Runs a step of the game on the network.
	 */
	public boolean runStep(Graph network)
	{
		Traverser traverser = traverserFactory.createTraverser(network);
		boolean finished = true;
		
		while (traverser.hasNext()) {
			List<Node> nodes = traverser.next();
			Delta c = findBestResponse(network, nodes);
			// c.applyTo(network); // fBR no longer uses a copy of the network!
			traverser.reportResult(c);
			if (!c.isEmpty())
				finished = false;
		}
		
		return finished;
	}
	
	/**
	 * Calculates the changes to the graph that the given node(s) wish to make.
	 * @param network the social network on which to run the calculations
	 * @param nodes the node(s) from the network in question
	 * @return the changes (if any) that the node(s) made
	 */
	protected abstract Delta findBestResponse(Graph network, List<Node> nodes);
	
	/* {} */
	
	public Map<Node,Rational> getUtilities(Graph network)
	{
		return utilCalc.getUtilities(network);
	}
	
	/**
	 * Returns the traverser factory.
	 * @return the traverser factory
	 */
	public TraverserFactory getTraverserFactory()
	{
	    return traverserFactory;
	}

	/**
	 * Sets the traverser factory
	 * @param newTraverserFactory new value for the traverser factory
	 */
	public void setTraverserFactory(TraverserFactory newTraverserFactory)
	{
	    traverserFactory = newTraverserFactory;
	}
	
	/**
	 * Returns the utility calculator.
	 * @return the utility calculator
	 */
	public UtilityCalculator getUtilityCalculator()
	{
	    return utilCalc;
	}

	/**
	 * Sets the utility calculator
	 * @param utilityCalculator new value for the utility calculator
	 */
	public void setUtilityCalculator(UtilityCalculator utilityCalculator)
	{
	    utilCalc = utilityCalculator;
	}
	
	/**
	 * Non-destructively runs a step of best-response dynamic on the given
	 * network. Returns true if the network is stable (i.e., if no changes
	 * were made by any node(s)).
	 * @return true if the network is stable
	 */
	public boolean isStable(Graph network)
	{
		return runStep(network.copy());
	}
	
	/**
	 * Returns the bounds of stability for the network on the game. The first
	 * element in the list will be the highest edge cost that prevents edge
	 * addition, and the second will be the lowest edge cost that prevents
	 * edge removal.
	 */
	public List<Rational> getCostBounds(Graph originalNetwork)
	{
		Graph network = originalNetwork;
		Delta changes = new Delta();

		Simulator.setEdgeCost(network, new Rational(0));
		Map<Node, Rational> initialValues = utilCalc.getUtilities(network);

		int n = network.size();
		Rational largestLowerStableAlpha = new Rational(-n * n);
		Rational smallestUpperStableAlpha = new Rational(n * n); //initial bounds

		Node[] nodes = new Node[n];
		int i = 0;
		for (Node inode : network) {
		    nodes[i++] = inode;
		}

		//Simulator.printNetwork(this, network);

		//for (List<Node> pair : traverser.makeIterable(network)) {
		for (i = 0; i < n; i++) {
		    for (int j = i + 1; j < n; j++) {
				Node a = nodes[i], b = nodes[j];
				
				//System.out.printf("a=%s; b=%s%n", a.getNeighbors(), b);
				
				if (network.connected(a, b)) { //try disconnecting them
				    network.disconnect(a, b);
				    
				    Map<Node, Rational> finalValues = utilCalc.getUtilities(network);
				    
				    Rational aDelta = finalValues.get(a).subtract(initialValues.get(a));
				    Rational bDelta = finalValues.get(b).subtract(initialValues.get(b));
				    
				    //if alpha > -deltaV ==> unstable
				    //so the upper bound on stability is -deltaV
				    //want to find the lowest upper bound on stability
				    
				    Rational stableAlphaLessThan =
				    	(aDelta.negate().lessThan(bDelta.negate())
				    		? aDelta.negate()
				    		: bDelta.negate());
				    
				    //printNetwork(clone);
				    
				    //System.out.println("stableAlphaLessThan = " + stableAlphaLessThan);
				    
				    smallestUpperStableAlpha =
				    	(stableAlphaLessThan.lessThan(smallestUpperStableAlpha)
				    		? stableAlphaLessThan
				    		: smallestUpperStableAlpha);
				    //System.out.println("smallestUpperStableAlpha = " + smallestUpperStableAlpha);
				   	
				   	network.connect(a, b);
				} else { //try connecting them
				    network.connect(a, b);
				    
				    Map<Node, Rational> finalValues = utilCalc.getUtilities(network);
				    
				    Rational aDelta = finalValues.get(a).subtract(initialValues.get(a));
				    Rational bDelta = finalValues.get(b).subtract(initialValues.get(b));
				    
				    //if alpha < deltaV ==> unstable
				    //so the lower bound on stability is the lower deltaV
				    //want to find the highest lower bound on stability
				    
				    Rational stableAlphaGreaterThan = (aDelta.lessThan(bDelta) ? aDelta : bDelta); //verified
				    
				    //Simulator.printNetwork(this, network);
				    
				    //System.out.println("stableAlphaGreaterThan = " + stableAlphaGreaterThan);
				    
				    largestLowerStableAlpha =
				    	(stableAlphaGreaterThan.greaterThan(largestLowerStableAlpha)
				    		? stableAlphaGreaterThan
				    		: largestLowerStableAlpha); //verified
				    //System.out.println("largestLowerStableAlpha = " + largestLowerStableAlpha);
				    
				    network.disconnect(a, b);
				}
		    }
		}
		    
		ArrayList<Rational> alphapair = new ArrayList<Rational>(2);
		
		alphapair.add(largestLowerStableAlpha);
		alphapair.add(smallestUpperStableAlpha);
		
		return alphapair;
	}
}
